/LMAR=50/TMAR=50/RMAR=4095/BMAR=1/PMAR=0/XLINE=0/FONT#0=NGR13/USETI=0000014*TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX**TEX*

␈β↓R␈↓ ↓H␈ε∩Demand␈αpaging.
␈β↓⎇␈↓ α⊂␈ε∩Consider␈α
a␈α∞program␈α
on␈α∞a␈α∞virtual␈α
machine␈α∞capable␈α
of␈α∞storing␈↓ 	]␈ελb␈↓ 	y␈ε∩\pages"␈α∞of␈α
a
␈βα(␈↓ ↓H␈ε∩|x␈α␈ed␈αsize␈αin␈αits␈αhigh-speed␈αmemory.␈αWhile␈αthe␈αprogram␈αis␈αrunning␈αit␈αreferences␈αa
␈βαS␈↓ ↓H␈ε∩sequence␈αof␈αpages␈αgiv␈α␈en␈αby␈αthe␈α\page␈αtrace"
␈ββ%␈↓ ¬l␈ελp␈↓ ε∩␈ελp␈↓ ε7␈εα.␈αε.␈αε.␈↓ εg␈ελp␈↓ π⊂␈εα.
␈ββ3␈↓ ¬⎇␈ε¬1␈↓ ε#␈ε¬2␈↓ εx␈εn
␈ββx␈↓ ↓H␈ε∩Suppose␈↓ αP␈ελS␈↓ αx␈ε∩is␈α	the␈α	set␈αλof␈↓ ∧/␈ελb␈↓ ∧F␈ε∩pages␈α	in␈αλhigh-speed␈α	memory␈α	just␈αλafter␈↓ 	~␈ελp␈↓ 	A␈ε∩is␈α	referenced;␈α	w␈α␈e
␈β∧¬␈↓ αb␈εj␈↓ 	+␈εj
␈β∧#␈↓ ↓H␈ε∩need␈↓ α~␈ελp␈↓ αB␈ε⊗2␈↓ αh␈ελS␈↓ βλ␈ε∩.␈αIf␈↓ β?␈ελp␈↓ βh␈ε⊗3␈↓ ∧∞␈ελS␈↓ ∧X␈ε∩,␈αa␈α
\page␈αfault"␈α
occurs;␈αsome␈αpage␈↓ λv␈ελq␈↓ 	≠␈ε∩in␈↓ 	C␈ελS␈↓ 
_␈ε∩is␈α
\pulled"
␈β∧0␈↓ α+␈εj␈↓ αz␈εj␈↓ βP␈εj␈↓ ∧ ␈εj␈↓ ∧-␈ε→␈␈ε¬1␈↓ 	β␈εj␈↓ 	U␈εj␈↓ 	b␈ε→␈␈ε¬1
␈β∧N␈↓ ↓H␈ε∩and␈α
w␈α␈e␈α∞hav␈α␈e␈↓ β≤␈ελS␈↓ βH␈εα=␈↓ βx␈ελS␈↓ ∧L␈ε⊗␈␈α	f␈↓ ¬␈ελq␈↓ ¬%␈ε⊗g␈εα␈α	+␈ε⊗␈α	f␈↓ ¬␈␈ελp␈↓ ε≥␈ε⊗g␈ε∩,␈α∞ex␈α␈changing␈↓ λβ␈ελp␈↓ λ/␈ε∩for␈↓ λh␈ελq␈↓ 	β␈ε∩.␈α⊂It␈α∞is␈α
con␈α␈v␈α␈enien␈α␈t␈α
to
␈β∧[␈↓ β.␈εj␈↓ ∧
␈εj␈↓ ∧↔␈ε→␈␈ε¬1␈↓ ¬_␈εj␈↓ ε⊂␈εj␈↓ λ∀␈εj␈↓ λu␈εj
␈β∧y␈↓ ↓H␈ε∩assume␈αthat␈αthe␈αprogram␈αstarts␈αout␈αwith␈αa␈αset␈↓ π+␈ελS␈↓ πW␈ε∩of␈↓ λ↓␈ελb␈↓ λ≤␈ε∩completely␈αn␈α␈ull␈αpages,␈αand
␈β¬π␈↓ π=␈ε¬0
␈β¬$␈↓ ↓H␈ε∩that␈↓ α⊗␈ελq␈↓ α:␈εα=␈↓ αh␈ελp␈↓ β∩␈ε∩when␈αthere␈αis␈αno␈αpage␈αfault.
␈β¬2␈↓ α#␈εj␈↓ αy␈εj
␈β¬P␈↓ α⊂␈ε∩It␈αεis␈απof␈απin␈α␈terest␈απto␈απconsider␈απthe␈απbest␈αεpossible␈απsequence␈απof␈απpage␈απpulls␈απ(the␈αεsequence
␈β¬{␈↓ ↓H␈ε∩that␈α
minimizes␈αthe␈α
total␈αn␈α␈um␈α␈ber␈α
of␈α
page␈αfaults)␈α
for␈αa␈α
giv␈α␈en␈αpage␈α
trace␈↓ 
⊃␈ελp␈↓ 
6␈ελp␈↓ 
\␈εα.␈αε.␈αε.␈↓ ␈ελp␈↓ 4␈ε∩,
␈βελ␈↓ 
"␈ε¬1␈↓ 
G␈ε¬2␈↓ ≥␈εn
␈βε&␈↓ ↓H␈ε∩ev␈α␈en␈α
though␈α∞it␈α
may␈α∞be␈α
impossible␈α∞actually␈α
to␈α∞achiev␈α␈e␈α
this␈α
optim␈α␈um␈α∞sequence␈α
in
␈βεQ␈↓ ↓H␈ε∩practice␈α∞because␈α∞it␈α∂may␈α∞require␈α∞kno␈α␈wing␈α∂the␈α∞future␈α∞page␈α∞requests␈↓ 	n␈ελp␈↓ 
=␈εα.␈αε.␈αε.␈↓ 
m␈ελp␈↓ ≡␈ε∩at
␈βε←␈↓ 	␈␈εj␈↓ 
␈ε¬+1␈↓ 
}␈εn
␈βε|␈↓ ↓H␈ε∩the␈αtime␈↓ αX␈ελq␈↓ α}␈ε∩m␈α␈ust␈αbe␈αchosen.
␈βπ
␈↓ αe␈εj
␈βπ2␈↓ ↓H␈ε∩a)␈α→(15␈αpoin␈α␈ts)
␈βπ↑␈↓ α⊂␈ε∩The␈αpurpose␈αof␈αthis␈αproblem␈αis␈αto␈αgiv␈α␈e␈αa␈αconstructiv␈α␈e␈αproof␈αthat␈αan␈αoptim␈α␈um
␈βλ	␈↓ ↓H␈ε∩strategy␈α
is␈αobtained␈α
by␈αthe␈α
follo␈α␈wing␈αrule:␈α∃\When␈↓ πb␈ελp␈↓ λ
␈ε⊗3␈↓ λ0␈ελS␈↓ λz␈ε∩,␈αlet␈↓ 	B␈ελq␈↓ 	f␈ε∩be␈αan␈α
elemen␈α␈t
␈βλ⊗␈↓ πs␈εj␈↓ λB␈εj␈↓ λO␈ε→␈␈ε¬1␈↓ 	O␈εj
␈βλ4␈↓ ↓H␈ε∩of␈↓ ↓v␈ελS␈↓ αQ␈ε∩that␈α⊂does␈α⊃not␈α⊂appear␈α⊃in␈ε⊗␈α⊂f␈↓ ¬w␈ελp␈↓ ε@␈εα,␈↓ εP␈εα.␈αε.␈αε.␈↓ π␈εα,␈↓ π⊂␈ελp␈↓ π3␈ε⊗g␈ε∩,␈α∩if␈α⊂possible.␈α~Otherwise␈α⊂(i.e.,␈α⊃if
␈βλA␈↓ αλ␈εj␈↓ α∃␈ε→␈␈ε¬1␈↓ ελ␈εj␈↓ ε∃␈ε¬+1␈↓ π!␈εn
␈βλ←␈↓ ↓H␈ε∩all␈αelemen␈α␈ts␈α
of␈↓ β9␈ελS␈↓ ∧⊂␈ε∩occur␈α
again),␈α
let␈↓ ε≤␈ελq␈↓ εC␈ε∩be␈α
the␈α
elemen␈α␈t␈αwhose␈α
|rst␈α
occurrence␈αin
␈βλm␈↓ βK␈εj␈↓ βX␈ε→␈␈ε¬1␈↓ ε)␈εj
␈β	
␈↓ ↓H␈ελp␈↓ α↔␈εα.␈αε.␈αε.␈↓ αG␈ελp␈↓ αv␈ε∩is␈ε∂␈αafter␈ε∩␈αall␈αthe␈αother␈αpages␈αof␈↓ εJ␈ελS␈↓ π ␈ε∩hav␈α␈e␈αoccurred."
␈β	_␈↓ ↓Y␈εj␈↓ ↓f␈ε¬+1␈↓ αX␈εn␈↓ ε\␈εj␈↓ εi␈ε→␈␈ε¬1
␈β	6␈↓ α⊂␈ε∩The␈α	proof␈α	can␈α
be␈α	obtained␈α
by␈α	repeatedly␈α	applying␈α
the␈α	follo␈α␈wing␈α
idea:␈α∩\Giv␈α␈en
␈β	a␈↓ ↓H␈ε∩a␈α
page␈α
trace␈↓ β∞␈ελp␈↓ β4␈ελp␈↓ βY␈εα.␈αε.␈αε.␈↓ ∧	␈ελp␈↓ ∧6␈ε∩and␈αa␈α
corresponding␈α
sequence␈αof␈α
page␈α
pulls␈↓ 	\␈ελq␈↓ 	}␈ελq␈↓ 
∨␈εα.␈αε.␈αε.␈↓ 
O␈ελq␈↓ 
x␈ε∩such
␈β	n␈↓ β∨␈ε¬1␈↓ βE␈ε¬2␈↓ ∧~␈εn␈↓ 	i␈ε¬1␈↓ 
␈ε¬2␈↓ 
\␈εn
␈β
␈↓ ↓H␈ε∩that,␈αλfor␈αλsome␈↓ β%␈ελj␈↓ β=␈ε∩with␈↓ ∧
␈ελp␈↓ ∧3␈ε⊗≤␈↓ ∧a␈ελq␈↓ ¬↓␈ε∩,␈αλthere␈αλis␈απan␈αλelemen␈α␈t␈↓ π8␈ελq␈↓ πR␈ε⊗2␈↓ πx␈ελS␈↓ λJ␈ε∩and␈αλan␈απindex␈↓ 
↔␈ελk␈↓ 
3␈εα>␈↓ 
a␈ελj␈↓ 
x␈ε∩such
␈β
→␈↓ ∧≠␈εj␈↓ ∧n␈εj␈↓ λ
␈εj␈↓ λ_␈ε→␈␈ε¬␈α␈1
␈β
7␈↓ ↓H␈ε∩that␈↓ α∪␈ελq␈↓ α-␈ε∩does␈α
not␈α	appear␈α
in␈↓ ∧T␈ελp␈↓ ¬#␈εα.␈αε.␈αε.␈↓ ¬S␈ελp␈↓ ¬|␈ε∩but␈↓ ε<␈ελq␈↓ ε`␈εα=␈↓ π∞␈ελp␈↓ π.␈ε∩,␈α
then␈α
there␈α	is␈α
another␈α
sequence␈α	of
␈β
E␈↓ ∧e␈εj␈↓ ∧r␈ε¬+1␈↓ ¬d␈εk␈↓ εI␈εj␈↓ π∨␈εk
␈β
]␈↓ α␈␈ε→0␈↓ β$␈ε→0␈↓ βx␈ε→0␈↓ ¬C␈ε→0␈↓ ε↔␈ε→0␈↓ λ}␈ε→0␈↓ 
4␈ε→0␈↓ 
X␈ε→0␈↓ -␈ε→0
␈β
b␈↓ ↓H␈ε∩page␈α
pulls␈↓ αo␈ελq␈↓ β∀␈ελq␈↓ β8␈εα.␈αε.␈αε.␈↓ βh␈ελq␈↓ ∧∃␈ε∩such␈αthat␈↓ ¬3␈ελq␈↓ ¬W␈εα.␈αε.␈αε.␈↓ επ␈ελq␈↓ εZ␈εα=␈↓ πλ␈ελq␈↓ π)␈εα.␈αε.␈αε.␈↓ πY␈ελq␈↓ λ*␈ε∩and␈↓ λn␈ελq␈↓ 	⊗␈εα=␈↓ 	D␈ελq␈↓ 	←␈ε∩and␈↓ 
#␈ελq␈↓ 
H␈ελq␈↓ 
l␈εα.␈αε.␈αε.␈↓ ≤␈ελq
␈β
p␈↓ π∃␈ε¬1␈↓ πf␈εj␈↓ πs␈ε→␈␈ε¬1
␈β
t␈↓ α␈␈ε¬1␈↓ β$␈ε¬2␈↓ βx␈εn␈↓ ¬C␈ε¬1␈↓ ε↔␈εj␈↓ ε%␈ε→␈␈ε¬␈α␈1␈↓ λ}␈εj␈↓ 
4␈ε¬1␈↓ 
X␈ε¬2␈↓ -␈εn
␈β∞␈↓ ↓H␈ε∩has␈αnot␈αmore␈αpage␈αfaults␈αthan␈↓ ¬.␈ελq␈↓ ¬O␈ελa␈↓ ¬t␈εα.␈αε.␈αε.␈↓ ε$␈ελq␈↓ εC␈ε∩."
␈β≠␈↓ ¬;␈ε¬1␈↓ ¬`␈ε¬2␈↓ ε1␈εn
␈β4␈↓ ¬∪␈ε→0␈↓ ¬7␈ε→0␈↓ ε␈ε→0
␈β9␈↓ α⊂␈ε∩The␈α∂required␈α∂sequence␈↓ ¬β␈ελq␈↓ ¬'␈ελq␈↓ ¬L␈εα.␈αε.␈αε.␈↓ ¬|␈ελq␈↓ ε-␈ε∩can␈α∂be␈α∂constructed␈α∂in␈α∂the␈α∂follo␈α␈wing␈α∂way:
␈βK␈↓ ¬∪␈ε¬1␈↓ ¬7␈ε¬2␈↓ ε␈εn
␈βd␈↓ ↓H␈ε∩Let␈↓ α∞␈ελm␈↓ α=␈ε∩be␈α⊂as␈α⊂large␈α⊂as␈α⊂possible␈α⊂such␈α⊂that␈↓ ε←␈ελq␈↓ ε␈␈ε∩does␈α⊂not␈α∂appear␈α⊂in␈↓ 	>␈ελq␈↓ 

␈εα.␈αε.␈αε.␈↓ 
:␈ελq␈↓ 
q␈ε∩or␈α∂in
␈βq␈↓ 	K␈εj␈↓ 	X␈ε¬+1␈↓ 
G␈εm
␈β∂␈↓ ↓H␈ελp␈↓ α↔␈εα.␈αε.␈αε.␈↓ αG␈ελp␈↓ αr␈ε∩.␈αLet␈↓ βJ␈ελr␈↓ βn␈εα=␈↓ ∧≤␈ελq␈↓ ∧6␈ε∩,␈αand␈αfor␈↓ ¬J␈ελj␈↓ ¬e␈εα<␈↓ ε∪␈ελi␈↓ ε+␈ε⊗∀␈↓ εY␈ελm␈↓ π∧␈ε∩let
␈β≥␈↓ ↓Y␈εj␈↓ ↓f␈ε¬+1␈↓ αX␈εm␈↓ βW␈εj␈↓ ∧)␈εj
␈βZ␈↓ ∧A␈ε→0
␈β←␈↓ ∧1␈ελq␈↓ ∧W␈εα=␈↓ ¬¬␈ελp␈↓ ¬!␈εα,␈↓ ¬O␈ελr␈↓ ¬q␈εα=␈↓ ε∨␈ελq␈↓ ε8␈εα,␈↓ π⊃␈ε∩if␈↓ π3␈ελp␈↓ πY␈εα=␈↓ λπ␈ελr␈↓ λK␈ε∩;
␈βm␈↓ ¬⊗␈εi␈↓ ¬\␈εi␈↓ ε,␈εi␈↓ πD␈εi␈↓ λ∀␈εi␈↓ λ ␈ε→␈␈ε¬1
␈βq␈↓ ∧A␈εi
␈β
⊂␈↓ ∧A␈ε→0
␈β
∃␈↓ ∧1␈ελq␈↓ ∧W␈εα=␈↓ ¬¬␈ελq␈↓ ¬≥␈εα,␈↓ ¬O␈ελr␈↓ ¬q␈εα=␈↓ ε∨␈ελr␈↓ εc␈εα,␈↓ π⊃␈ε∩otherwise.
␈β
#␈↓ ¬∩␈εi␈↓ ¬\␈εi␈↓ ε,␈εi␈↓ ε8␈ε→␈␈ε¬1
␈β
'␈↓ ∧A␈εi
␈β
`␈↓ ∧#␈ε→0␈↓ εg␈ε→0
␈β
e␈↓ ↓H␈ε∩Finally␈αif␈↓ αf␈ελm␈↓ β∂␈εα<␈↓ β=␈ελn␈↓ β←␈ε∩let␈↓ ∧∪␈ελq␈↓ ∧r␈εα=␈↓ ¬ ␈ελr␈↓ ¬G␈ε∩,␈αand␈αlet␈↓ εW␈ελq␈↓ ε⎇␈εα=␈↓ π+␈ελq␈↓ πO␈ε∩for␈↓ λπ␈ελm␈↓ λ/␈εα+␈αλ1␈α
<␈↓ 	%␈ελi␈↓ 	=␈ε⊗∀␈↓ 	k␈ελn␈↓ 
␈ε∩.
␈β
r␈↓ ¬-␈εm␈↓ π8␈εi
␈β
w␈↓ ∧#␈εm␈↓ ∧=␈ε¬+1␈↓ εg␈εi
␈β∞␈↓ βY␈ε→0␈↓ λt␈ε→0
␈β∞⊂␈↓ α⊂␈ε∩Pro␈α␈v␈α␈e␈αthat␈↓ βC␈ελS␈↓ βo␈εα=␈↓ ∧≡␈ελS␈↓ ∧D␈ε⊗␈␈αλf␈↓ ¬α␈ελq␈↓ ¬∩␈ε⊗g␈εα␈αλ+␈ε⊗␈αλf␈↓ ¬j␈ελr␈↓ εβ␈ε⊗g␈ε∩␈αfor␈↓ εZ␈ελj␈↓ εu␈ε⊗∀␈↓ π#␈ελi␈↓ π<␈ε⊗∀␈↓ πk␈ελm␈↓ λ↔␈ε∩and␈↓ λ]␈ελS␈↓ 	
␈εα=␈↓ 	9␈ελS␈↓ 	c␈ε∩for␈αall␈↓ 
M␈ελi␈↓ 
f␈εα>␈↓ ∃␈ελm␈↓ 4␈ε∩.
␈β∞≥␈↓ ∧0␈εi␈↓ ¬w␈εi␈↓ 	K␈εi
␈β∞"␈↓ βY␈εi␈↓ λt␈εi
␈β∞6␈↓ εi␈ε→0␈↓ π∞␈ε→0␈↓ πb␈ε→0
␈β∞;␈↓ ↓H␈ε∩And␈α	pro␈α␈v␈α␈e␈α
that␈α
the␈α	sequence␈α
of␈α
page␈α
pulls␈↓ εY␈ελq␈↓ ε}␈ελq␈↓ π"␈εα.␈αε.␈αε.␈↓ πR␈ελq␈↓ π}␈ε∩has␈α
no␈α	more␈α
page␈α
faults␈α	than
␈β∞M␈↓ εi␈ε¬1␈↓ π∞␈ε¬2␈↓ πb␈εn
␈β∞f␈↓ ↓H␈ελq␈↓ ↓i␈ελq␈↓ α
␈εα.␈αε.␈αε.␈↓ α:␈ελq␈↓ αY␈ε∩.
␈β∞t␈↓ ↓U␈ε¬1␈↓ ↓v␈ε¬2␈↓ αG␈εn
␈β∂.␈↓ ε:␈εα1
␈β⊃∂

␈β↓P␈↓ ↓H␈ε∩b)␈α→(5␈αpoin␈α␈ts)
␈β↓{␈↓ α⊂␈ε∩One␈αλof␈αλthe␈αλpage␈α	pulling␈αλalgorithms␈αλaften␈αλused␈αλin␈α	practice␈αλis␈αλthe␈αλso-called␈αλ\least
␈βα&␈↓ ↓H␈ε∩recen␈α␈tly␈αused"␈α
rule:␈α~If␈↓ ∧:␈ελp␈↓ ∧c␈ε⊗3␈↓ ¬
␈ελS␈↓ ¬T␈ε∩,␈α
the␈αpage␈↓ ε}␈ελq␈↓ π%␈ε∩that␈αis␈α
pulled␈αis␈α
a␈αn␈α␈ull␈αpage␈α
if␈αan␈α␈y
␈βα4␈↓ ∧K␈εj␈↓ ¬≤␈εj␈↓ ¬)␈ε→␈␈ε¬1␈↓ π␈εj
␈βαQ␈↓ ↓H␈ε∩n␈α␈ull␈α
pages␈α
are␈α	presen␈α␈t,␈αotherwise␈↓ ¬J␈ελq␈↓ ¬n␈ε∩is␈α
the␈α
page␈α
whose␈α
last␈α
occurrence␈α
in␈↓ 
 ␈ελp␈↓ 
E␈εα.␈αε.␈αε.␈↓ 
u␈ελp
␈βα←␈↓ ¬W␈εj␈↓ 
1␈ε¬1␈↓ ε␈εj␈↓ ∪␈ε→␈␈ε¬1
␈βα⎇␈↓ ↓H␈ε∩comes␈αbefore␈αoccurrences␈αof␈αall␈αthe␈αother␈αpages␈αin␈↓ πb␈ελS␈↓ λ,␈ε∩.
␈ββ
␈↓ πt␈εj␈↓ λ↓␈ε→␈␈ε¬1
␈ββ(␈↓ α⊂␈ε∩Construct␈αa␈α
page␈αtrace␈α
scheme␈α
for␈αwhich␈α
this␈αrule␈α
leads␈α
to␈αabout␈↓ 
#␈ελb␈↓ 
>␈ε∩times␈αas
␈ββS␈↓ ↓H␈ε∩man␈α␈y␈αpage␈αfaults␈αas␈αthe␈αoptim␈α␈um␈αstrategy␈αdoes.
␈β∂.␈↓ ε:␈εα2
␈β⊃∂/FONT#2=cmr10[XGP,SYS]=+,.12<=>>/FONT#5=cmr7[XGP,SYS]=+0122/FONT#8=cmi10[XGP,SYS]=Sabijkmnpqrr/FONT#11=cmi7[XGP,SYS]=ijkmnn/FONT#15=cms10[XGP,SYS]=aefrtt/FONT#18=cmb10[XGP,SYS]="(),-.15:;ACDFGILOPSTW\abcdefghijklmnopqrstuvwxyz||/FONT#22=cmsy10[XGP,SYS]=∀≤23fgg/FONT#25=cmsy7[XGP,SYS]=00